package algorithm.MonotonePriorityStack.template;

import java.util.Stack;

/**
 * description :
 * author Ahang :
 * create : 2025-08-21 11:36
 */
public class Class {
    /**
     * @Description: 单调栈模板
     * @Param:
     * @return:
     * @Author: ahang
     * @Date: 2025/8/21
     */
    public int[][] template(int[] arr) {
        int n = arr.length;
        int[][] ans = new int[n][2];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                int temp = stack.pop();
                ans[temp][0] = stack.isEmpty() ? -1 : stack.peek();
                ans[temp][1] = i;
            }
            stack.push(i);
        }
        // 清算阶段
        while (!stack.isEmpty()) {
            int temp = stack.pop();
            ans[temp][0] = stack.isEmpty() ? -1 : stack.peek();
            ans[temp][1] = -1;
        }
//        检查阶段
        for (int i = n-2; i >= 0; i--){
            if (ans[i][1]!=-1&&arr[i]==arr[ans[i][1]]){
                ans[i][1] = ans[ans[i][1]][1];
            }
        }
        return ans;

    }

}
